package backtrack;

import java.util.ArrayList;

/**
 * @author le
 */
public class AllSubCollections
{
    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int[] arr = {1, 2, 3};
        res = subsets(arr);
        for(ArrayList<Integer> s : res){
            System.out.println(s.toString());
        }
    }

    public static ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int[] used = new int[S.length];
        backtrack(0, S, res, used);
        return res;
    }

    public static void backtrack(int k,int[] s,ArrayList<ArrayList<Integer>> res,int[] used){
        if (k == s.length){
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < s.length;i++){
                if (used[i] == 1){
                    tmp.add(s[i]);
                }
            }
            res.add(tmp);
            tmp.forEach(System.out::println);

        }else{
            used[k] = 0;
            backtrack(k+1, s, res, used);
            used[k] = 1;
            backtrack(k+1, s, res, used);
        }
    }
}
